package berkeley.lab6.sortedlist;

/* SortedList.java */
import java.util.Enumeration;

/**
 * The SortedList class is a singly-linked implementation of a linked list in sorted order. SortedLists are mutable data
 * structures that can grow at either end.
 *
 * @author Kathy Yelick, Bob Zasio
 *
 */
public class SortedList {

    private int size;
    ListNode head;

    /**
     * Construct an empty list
   *
     */
    public SortedList() {
        size = 0;
        head = null;
    }

    /**
     * isEmpty() returns true if this list is empty, false otherwise.
     *
     * @return true if the list is empty, false otherwise.
   *
     */
    public boolean isEmpty() {
        return (size == 0);
    }

    /**
     * length() returns the length of this list.
     *
     * @return the length of the list.
   *
     */
    public int length() {
        return size;
    }

    /**
     * insert() inserts the element x into the proper sorted location.
   *
     */
    public void insert(Keyable x) {
        ListNode newnode = new ListNode(x, null);

        if (head == null) {
            head = newnode;
        } else if (!head.item.lessThan(x)) {
            newnode.next = head;
            head = newnode;
        } else {
            ListNode temp = head;
            while (temp.next != null) {
                if (!temp.next.item.lessThan(x)) {
                    newnode.next = temp.next;
                    temp.next = newnode;
                    temp = temp.next;
                    break;
                }
                temp = temp.next;
            }
            if (temp.next == null) {
                temp.next = newnode;
            }
        }
        size++;
    }

    /**
     * Keyable() returns the element with the given key, or null if none of the elements have that key.
   *
     */
    public Keyable find(int key) {
        ListNode temp = head;
        while (temp != null) {
            if (temp.item.getKey() == key) {
                return temp.item;
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * elements() returns an Enumeration of the components of this list.
     *
     * @return an Enumeration of the components of this list.
   *
     */
    public Enumeration elements() {
        return new ListEnum(head);
    }

    /**
     * toString() returns a String representation of this list.
     *
     * @return a String representation of this list.
   *
     */
    public String toString() {
        int i;
        Object obj;
        String result = "[  ";

        ListNode cur = head;

        while (cur != null) {
            obj = cur.item;
            result = result + obj.toString() + "  ";
            cur = cur.next;
        }
        result = result + "]";
        return result;
    }
}
